/**
 * @version Create on 2012-10-31
 * @author Yinzi Chen
 */

public class ConvertSortedArrayToBST {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode buildTree(int[] num, int l, int r) {
		if (l > r)
			return null;
		int n = r - l + 1;
		TreeNode root = new TreeNode(num[l + n / 2]);
		root.left = buildTree(num, l, l + n / 2 - 1);
		root.right = buildTree(num, l + n / 2 + 1, r);
		return root;
	}

	public TreeNode sortedArrayToBST(int[] num) {
		return buildTree(num, 0, num.length - 1);
	}

	public static void main(String[] args) {

	}

}
